package E_2024;

import java.util.Arrays;

/*
    为了提升软件编码能力，小王制定了刷题计划，他选了题库中的n道题，
    编号从0到n-1，并计划在m天内按照题目编号顺序刷完所有的题目(注意，小王不能用多天完成同一题)
    在小王刷题计划中，小王需要用time[i]的时间完成编号i的题目此外，
    小王还可以查看答案，可以省去该题的做题时间。为了真正达到刷题效果，
    小王每天最多直接看一次答案。我们定义m天中做题时间最多的一天耗时为T(直接看答案的题目不计入做题总时间)。
    请你帮小王求出最小的T是多少
输入描述
    第一行输入为time,time[i]的时间完成编号i的题目
    第二行输入为m，m表示几天内完成所有题目，1<= m<= 180
输出描述
    最小耗时整数T
示例1:
    输入
    999,999,999
    4
    输出
    0
    说明
    在前三天中，小王每天都直接看答案，这样他可以在三天内完成所有的题目并不花任何时间
示例2:
    输入
    1,2,2,3,5,4,6,7,8
    5
    输出
    4
    说明
    第一天完成前3题，第3题看答案；
    第二天完成第4题和第5题，第5题看答案；
    第三天完成第6和第7题，第7题看答案；
    第四天完成第8题，直接看答案；
    第五天完成第9题，直接看答案
    7 4
    3 0  4
    3 4  4
    0 1  7


 */
public class E_200_24 {
    public static void main(String[] args) {
        ans(new int[]{1,2,2,3,5,4,6,7,8},5);
        System.out.println(ans);
    }
    static int ans = Integer.MAX_VALUE;
    public static int ans(int[] arr, int m){
        if (arr.length <= m) return 0;
        dfs(arr,0, m, new int[m+1]);
        return 1;
    }
    public static void dfs(int[] arr , int index, int m, int[] days){
        if (m == 1){
            int sum = 0;
            int max = 0;
            for (int i = index; i < arr.length; i++) {
                sum += arr[i];
                max = Math.max(max,arr[i]);
            }
            days[m] = sum - max;
            max = 0;
            for (int day : days) {
                max = Math.max(max,day);
            }
            ans = Math.min(max,ans);
            System.out.println(Arrays.toString(days));
            return;
        }
        // 需要保证每天最少一题
        for (int i = index; i < arr.length - m + 1; i++) {
            int sum = 0;
            int max = 0;
            for (int k = index; k <= i; k++) {
                sum += arr[k];
                max = Math.max(max,arr[k]);
            }
            int x = sum - max;
            days[m] = x;
            dfs(arr, i + 1, m - 1,days);
        }
    }
}
